package com.wtgroup.demo.leetcode.org_bytedance;

import com.wtgroup.demo.common.bean.LinkNode;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 60906
 * @date 2021/5/5 22:06
 */
public class Q_环形链表II {

    @Test
    public void foo() {
        // 3,2,0,-4
        LinkNode n0 = new LinkNode(3);
        LinkNode n1 = new LinkNode(2);
        LinkNode n2 = new LinkNode(0);
        LinkNode n3 = new LinkNode(-4);
        n0.next = n1;
        n1.next = n2;
        n2.next = n3;
        n3.next = n1;

        LinkNode res = new Solution_LC_2().detectCycle(n0);
        System.out.println(res);
    }


    /**
     * O(N) 空间复杂度解决
     */
    private class Solution_LC_1 {
        public LinkNode detectCycle(LinkNode head) {
            if (head == null || head.next == null) {
                return null;
            }
            Map<LinkNode, Integer> registry = new HashMap<>();
            LinkNode cur = head;
            while (cur != null) {
                if (registry.containsKey(cur)) {
                    return cur;
                }
                registry.put(cur, null);
                cur = cur.next;
            }
            return null;
        }
    }

    /**
     * O(1)
     * 有趣的三角恋.
     * 慢男追快女, 追呀追, 追到后.
     * 这时, 冒出一只狗, 恨呀, 要追慢男, 修理他.
     * 慢男跑呀, 狗就追呀, 速度一样.
     * 追上了, 就是环的入口了.
     */
    private class Solution_LC_2 {

        public LinkNode detectCycle(LinkNode head) {
            if (head == null || head.next == null) {
                return null;
            }

            LinkNode girl = head;
            LinkNode boy = head;
            while (girl != null) {
                girl = girl.next != null ? girl.next.next : null;
                boy = boy.next;
                // boy 追上 girl 了 , 这时, 来了跳狗, 追男孩
                if (girl == boy) {
                    // boy 追上 girl 了
                    LinkNode dog = head;
                    while (dog != boy) {
                        dog = dog.next;
                        boy = boy.next;
                    }

                    return dog;
                }
            }

            // 链表有尽头 => 没有环
            return null;
        }
    }

}
